Cours 10 : Régression logistique

Loïc Grobol lgrobol@parisnanterre.fr

2021-10-27

Vectorisations arbitraires de documents

On a vu des façons de traiter des documents vus comme des sacs des mots en les représentant comme des vecteurs dont les coordonnées correspondaient à des nombres d'occurrences.

Mais on aimerait — entre autres — pouvoir travailler avec des représentations arbitraires, on peut par exemple imaginer vouloir représenter un document par ŀa polarité (au sens de l'analyse du sentiment) de ses mots.

🧠 Exo 🧠

1. Vectoriser un document

À l'aide d'un lexique de sentiment (par exemple VADER), écrivez une fonction qui prend en entrée un texte en anglais et renvoie sa représentation sous forme d'un vecteur de features à deux traits : polarité positive moyenne (la somme des polarités positives des mots qu'il contient divisée par sa longueur en nombre de mots) et polarité négative moyenne.

🧠 Correction 1 🧠

On commence par recycler notre tokenizer/normaliseur

On lit le lexique

Et voilà comment on récupère la représentation d'un document

On teste ?

2. Vectoriser un corpus

Appliquer la fonction précédente sur le mini-corpus IMDB

🧠 Correction 2 🧠

Commençons par l'extraire

Maintenant on parcourt le dossier pour construire nos représentations

Visualisation

Comment se répartissent les documents du corpus avec la représentation qu'on a choisi

On voit des tendances qui se dégagent, mais clairement ça va être un peu coton

Classifieur linéaire

On considère des vecteurs de features de dimension $n$

$$\mathbf{x} = (x₁, …, x_n)$$

Un vecteur de poids de dimension $n$

$$\mathbf{w} = (w₁, …, w_n)$$

et un biais $b$ scalaire (un nombre quoi).

Pour réaliser une classification on considère le nombre $z$ (on parle parfois de logit)

$$z=w₁×x₁ + … + w_n×x_n + b = \sum_iw_ix_i + b$$

Ce qu'on note aussi

$$z = \mathbf{w}⋅\mathbf{x}+b$$

$\mathbf{w}⋅\mathbf{x}$ se lit « w scalaire x », on parle de produit scalaire en français et de inner product en anglais.

(ou pour les mathématicien⋅ne⋅s acharné⋅e⋅s $z = \langle w\ |\ x \rangle + b$)

Quelle que soit la façon dont on le note, on affectera à $\mathbf{x}$ la classe $0$ si $z < 0$ et la classe $1$ sinon.

😴 Exo 😴

1. Une fonction affine

Écrire une fonction qui prend en entrée un vecteur de features et un vecteur de poids sous forme de tableaux numpy $x$ et $w$ de dimensions (n,) et un biais $b$ sous forme d'un tableau numpy de dimensions (1,) et renvoie $z=\sum_iw_ix_i + b$.

😴 Correction 1 😴

Une version élémentaire avec des boucles

Une version plus courte avec les fonctions natives de numpy

2. Un classifieur linéaire

Écrire un classifieur linéaire qui prend en entrée des vecteurs de features à deux dimensions précédents et utilise les poids respectifs $0.6$ et $-0.4$ et un biais de $-0.01$. Appliquez ce classifieur sur le mini-corpus IMDB qu'on a vectorisé et calculez son exactitude.

😴 Correction 2 😴

On commence par définir le classifieur : on va renvoyer True pour la classe positive et False pour la classe négative.

Maintenant on le teste

On en fait une fonction, ça nous sera utile plus tard

Classifieur linéaire ?

Pourquoi linéaire ? Regardez la figure suivante qui colore les points $(x,y)$ du plan en fonction de la valeur de $z$.

Ou encore plus clairement, si on représente la classe assignée

On voit bien que la frontière de classification est une droite, a line. On a donc un linear classifier : un classifieur linéaire (même si en français on dirait qu'il s'agit d'une fonction affine).

Qu'est-ce que ça donne si on superpose avec notre corpus ?

Pas si surprenant que nos résultats ne soient pas terribles…

La fonction logistique

$$σ(z) = \frac{1}{1 + e^{−z}} = \frac{1}{1 + \exp(−z)}$$

Elle permet de normaliser $z$ : $z$ peut être n'importe quel nombre entre $-∞$ et $+∞$, mais on aura toujours $0 < σ(z) < 1$, ce qui permet de l'interpréter facilement comme une vraisemblance. Autrement dit, $σ(z)$ sera proche de $1$ s'il paraît vraisemblable que $x$ appartienne à la classe $1$ et proche de $0$ sinon.

📈 Exo 📈

Tracer avec matplotlib la courbe représentative de la fonction logistique.

📈 Correction 📈

Régression logistique

Formellement : on suppose qu'il existe une fonction $f$ qui prédit parfaitement les classes, donc telle que pour tout couple exemple/étiquette $(x, y)$ avec $y$ valant $0$ ou $1$, $f(x) = y$. On approcher cette fonction par une fonction $g$ de la forme

$$g(x) = σ(w⋅x+b)$$

Si on choisit les poids $w$ et le biais $b$ tels que $g$ soit la plus proche possible de $f$ sur notre ensemble d'apprentissage, on dit que $g$ est la régression logistique de $f$ sur cet ensemble.

Un classifieur logistique, c'est simplement un classifieur qui pour un exemple $x$ renvoie $0$ si $g(x) < 0.5$ et $1$ sinon. Il a exactement les mêmes capacités de discrimination qu'un classifieur linéaire (sa frontière de décision est la même et il ne sait donc pas prendre de décisions plus complexes), mais on peut interpréter la confiance qu'il a dans sa décision.

Par exemple voici la confiance que notre classifieur codé en dur a en ses décisions

Quelle est la vraisemblance de la classe $0$ (review négative) ? Et bien le reste

Comme l'exemple en question appartient bien à cette classe, ça signifie que notre classifieur et plutôt bon sur cet exemple. L'est-il sur le reste du corpus ?

Autrement dit, pour un exemple pris au hasard dans le corpus, la vraisemblance de sa classe telle que jugée par le classifieur sera de $50.49\%$. Un classifieur parfait obtiendrait $100\%$, un classifieur qui prendrait systématiquement la mauvaise décision $0\%$ et un classifieur aléatoire uniforme $50\%$ (puisque notre corpus a autant d'exemples de chaque classe).

Moralité : nos poids ne sont pas très bien choisis, et notre préoccupation dans la suite va être de chercher comment choisir des poids pour que la confiance moyenne de la classe correcte soit aussi haute que possible.

Fonction de coût

On a dit que notre objectif était

Chercher les poids $w$ et le biais $b$ tels que $g$ soit la plus proche possible de $f$ sur notre ensemble d'apprentissage

On formalise « être le plus proche possible » de la section précédente comme minimiser une certaine fonction de coût (loss) $L$ qui mesure l'erreur faite par le classifieur sur un exemple.

$$L(g(x), y) = \text{l'écart entre la classe prédite par $g$ pour $x$ et la classe correcte $y$}$$

Étant donné un ensemble de test $(x₁, y₁), …, (x_n, y_n)$, on estime l'erreur faite par le classifieur logistique $g$ pour chaque exemple $(x_i, y_i)$ comme le coût local $L(g(xᵢ), yᵢ)$ et son erreur sur tout l'ensemble de test par le coût global $\mathcal{L}$ :

$$\mathcal{L} = \sum_i L(g(xᵢ), yᵢ)$$

Plus $\mathcal{L}$ sera bas, meilleur sera notre classifieur.

Dans le cas de la régression logistique, on va s'inspirer de ce qu'on a vu dans la section précédente et utiliser la log-vraisemblance négative (negative log-likelihood) :

On définit la vraisemblance $V$ comme précédemment par $$ V(a, y) = \begin{cases} a & \text{si $y = 1$}\\ 1-a & \text{sinon} \end{cases} $$

Intuitivement, il s'agit de la vraisemblance affectée par le modèle à la classe correcte $y$. Il ne s'agit donc pas d'un coût, mais d'un gain (si sa valeur est haute, c'est que le modèle est bon)

La log-vraisemblance négative $L$ est alors définie par

$$L(a, y) = -\log(V(a, y))$$

Le $\log$ est là pour plusieurs raisons, calculatoires et théoriques1 et le $-$ à s'assurer qu'on a bien un coût (plus la valeur est basse, meilleur le modèle est).

1. Entre autres, comme pour *Naïve Bayes*, parce qu'une somme de $\log$-vraisemblance peut être vue comme le $\log$ de la probabilité d'une conjonction d'événements indépendants. Mais surtout parce qu'il rend la fonction de coût **convexe** par rapport à $w$.

Une interprétation possible : $L(a, y)$, c'est la surprise de $y$ au sens de la théorie de l'information. Autrement dit : si j'estime qu'il y a une probabilité $a$ d'observer la classe $y$, $L(a, y)$ mesure à quel point il serait surprenant d'observer effectivement $y$.

On peut vérifier qu'il s'agit bien d'un coût :

On peut aussi vérifier facilement que $L(a, 1)$ est décroissant par rapport à $a$ et que $L(1-a, 0)$ est croissant par rapport à $a$. Autrement dit, plus le classifieur juge que la classe correcte est vraisemblable plus le coût $L$ est bas.

Enfin, on peut l'écrire $L$ en une ligne : pour un exemple $x$, le coût de l'exemple $(x, y)$ est

$$L(g(x), y) = -\log\left[g(x)×y + (1-g(x))×(1-y)\right]$$

C'est un trick, l'astuce c'est que comme $y$ vaut soit $0$ soit $1$, soit $y=0$, soit $1-y=0$ et donc la somme dans le $\log$ se simplifie dans tous les cas. Rien de transcendant là-dedans.

La formule diffère un peu de celle de Speech and Language Processing, mais les résultats sont les mêmes et celle-ci est mieux pour notre problème !

En fait la leur est la formule générale de l'entropie croisée pour des distributions de proba à support dans $\{0, 1\}$, ce qui est une autre intuition pour cette fonction de coût, mais ici elle nous complique la vie.

Une dernière façon de l'écrire en une ligne :

$$L(g(x), y) = -\log\left[g(x)\mathbb{1}_{y=1} + (1-g(x))\mathbb{1}_{y=0}\right]$$

📉 Exo 📉

Écrire une fonction qui prend en entrée

Et renvoie la log-vraisemblance négative du classifieur logistique de poids $(w, b)$ pour l'exemple $(x, y)$.

Servez-vous en pour calculer le coût du classifieur de l'exercise précédent sur le mini-corpus IMDB.

📉 Correction 📉

Avec des compréhensions

En version numériquement stable

Descente de gradient

Principe général

L'algorithme de descente de gradient est la clé de voute de l'essentiel des travaux en apprentissage artificiel moderne. Il s'agit d'un algorithme itératif qui étant donné un modèle paramétrisé et une fonction de coût (avec des hypothèses de régularité assez faibles) permet de trouver des valeurs des paramètres pour lesquelles la fonction de coût est minimal.

On ne va pas rentrer dans les détails de l'algorithme de descente de gradient stochastique, mais juste essayer de se donner quelques idées.

L'intuition à avoir est la suivante : si vous êtes dans une vallée et que vous voulez trouver rapidement le point le plus bas, une façon de faire est de chercher la direction vers laquelle la pente descend le plus vite, de faire quelques pas dans cette direction puis de recommencer. On parle aussi pour cette raison d'algorithme de la plus forte pente.

Clairement une condition pour que ça marche peu importe le point de départ, c'est que la vallée n'ait qu'un seul point localement le plus bas. Par exemple ça marche avec une vallée comme celle-ci

Mais pas pour celle-là

OK, mais comment on trouve la plus forte pente en pratique ? En une dimension il suffit de suivre l'opposé du nombre dérivé : https://uclaacm.github.io/gradient-descent-visualiser/#playground

En plus de dimensions, c'est plus compliqué, mais on peut s'en sortir en suivant le gradient qui est une généralisation du nombre dérivé : https://jackmckew.dev/3d-gradient-descent-in-python.html

Ce qui fait marcher la machine c'est que le gradient indique la direction dans laquelle la fonction croît le plus vite. Et que l'opposé du gradient indique la direction dans laquelle la fonction décroît le plus vite.

(localement)

Concrètement si on veut trouver $\theta$ tel que $f(\theta)$ soit minimale pour une certaine fonction $f$ dont le gradient est donné par grad_f ça donne l'algo suivant

def descent(grad_f, theta_0, learning_rate, n_steps):
    theta = theta_0
    for _ in range(n_steps):
        # On trouve la direction de plus grande pente
        steepest_direction = -grad_f(theta)
        # On fait quelques pas dans cette direction
        theta += learning_rate*steepest_direction
    return theta

Les hyperparamètres sont

Ici on se donne un nombre fixe d'epochs, une autre possibilité serait de s'arrêter quand on ne bouge plus trop, par exemple avec une condition comme

if np.max(grad_f(theta)) < 0.00001:
    break

dans la boucle et éventuellement avec une boucle infinie while True.

Point notation :

Descente de gradient stochastique

Rappelez-vous, on a dit que notre fonction de coût, c'était

$$\mathcal{L} = \sum_i L(g(xᵢ), yᵢ)$$

et on cherche la valeur du paramètre $θ = (w_1, …, w_n, b)$ tel que $\mathcal{L}$ soit le plus petit possible.

On peut utilise la propriété d'additivité du gradient : pour deux fonctions $f$ et $g$, on a

$$\operatorname{grad}(f+g) = \operatorname{grad}f + \operatorname{grad}g$$

Donc ici

$$\operatorname{grad}\mathcal{L} = \sum_i \operatorname{grad}L(g(xᵢ), yᵢ)$$

Si on dispose d'une fonction grad_L qui, étant donnés $g(x_i)$ et $y_i$, renvoie $\operatorname{grad}L(g(x_i), y_i)$, l'algorithme de descente du gradient devient alors

def descent(train_set, theta_0, learning_rate, n_steps):
    theta = theta_0
    for _ in range(n_steps):
        w = theta[:-1]
        b = theta[-1]
        partial_grads = []
        for (x, y) in train_set:
            # On calcule g(x)
            g_x = logistic(np.inner(w,x)+b)
            # On calcule le gradient de L(g(x), y))
            partial_grads.append(grad_L(g_x, y))
        # On trouve la direction de plus grande pente
        steepest_direction = -np.sum(partial_grads)
        # On fait quelques pas dans cette direction
        theta += learning_rate*steepest_direction

    return theta

Pour chaque étape, on doit calculer tous les $g(x_i)$ et $\operatorname{grad}L(g(x_i), y_i)$. C'est très couteux, il doit y avoir moyen de faire mieux.

Si les $L(g(xᵢ), yᵢ)$ étaient indépendants, ce serait plus simple : on pourrait les optimiser séparément.

Ce n'est évidemment pas le cas : si on change $g$ pour que $g(x_0)$ soit plus proche de $y_0$, ça changera aussi la valeur de $g(x_1)$.

Mais on va faire comme si

C'est une approximation sauvage, mais après tout on commence à avoir l'habitude. On va donc suivre l'algo suivant

def descent(train_set, theta_0, learning_rate, n_steps):
    theta = theta_0
    for _ in range(n_steps):
        for (x, y) in train_set:
            w = theta[:-1]
            b = theta[-1]
            # On calcule g(x)
            g_x = logistic(np.inner(w,x)+b)
            # On trouve la direction de plus grande pente
            steepest_direction = -grad_L(g_x, y)
            # On fait quelques pas dans cette direction
            theta += learning_rate*steepest_direction

    return theta

Faites bien attention à la différence : au lieu d'attendre d'avoir calculé tous les $\operatorname{grad}L(g(x_i), y_i)$ avant de modifier $θ$, on va le modifier à chaque fois.

Notre espoir ici c'est que cette situation n'arrivera pas, et qu'on bon paramètre pour un certain couple $(x, y)$ c'est un bon paramètres pour $tous$ les couples (exemple, classe).

Ce nouvel algorithme s'appelle l'algorithme de descente de gradient stochastique, et il est crucial pour nous, parce qu'on ne pourra en pratique quasiment jamais faire de descente de gradient globale.

Il ne nous reste plus qu'à savoir comment on calcule grad_L. On ne fera pas la preuve, mais on a

$$\frac{∂L(g(x), y)}{∂w_i} = (g(x)-y)x_i$$

et

$$\frac{∂L(g(x), y)}{∂b} = g(x)-y$$

Autrement dit on mettra à jour $w$ en calculant

$$w ← w -η×\operatorname{d}_wL(g(x), y) = w - η×(g(x)-y)x$$

$\operatorname{d}_wL(g(x), y) = \left(\frac{∂L(g(x), y)}{∂w_1}, …, \frac{∂L(g(x), y)}{∂w_n}\right)$ est la *différentielle partielle* de $L(g(x), y)$ par rapport à $w$.

Et $b$ en calculant

$$b ← b -η×\frac{∂L(g(x), y)}{∂b} = b - η×(g(x)-y)$$

🧐 Exo 🧐

1. Calculer le gradient

Reprendre la fonction qui calcule la fonction de coût, et la transformer pour qu'elle renvoie le gradient par rapport à $w$ et la dérivée partielle par rapport à $b$ en $(x, y)$.

🧐 Correction 1 🧐

2. Descendre le gradient

S'en servir pour apprendre les poids à donner aux features précédentes à l'aide du mini-corpus IMDB en utilisant l'algorithme de descente de gradient stochastique.

🧐 Correction 2 🧐

Version minimale

Avec du feedback pour voir ce qui se passe

Un peu de visu supplémentaire :

Le trajet fait par $θ$ au cours de l'apprentissage

Régression multinomiale

Un dernier point : on a vu dans tout ceci comment utiliser la régression logistique pour un problème de classification à deux classes. Comment on l'étend à $n$ classes ?

Réflechissons déjà à quoi ressemblerait la sortie d'un tel classifieur :

Pour un problème à deux classes, le classifieur $g$ nous donne pour chaque exemple $x$ une estimation $g(x)$ de la vraisemblance de la classe $1$, et on a vu que la vraisemblance de la classe $0$ était nécessairement $1-g(x)$ pour que la somme des vraisemblances fasse 1.

On peut le présenter autrement : considérons le classifieur $f$ tel que pour tout exemple $x$

$$f(x) = (1-g(x), g(x))$$

$f$ nous donne un vecteur à deux coordonnées, $f_0(x)$ et $f_1(x)$, qui sont respectivement les vraisemblances des classes $0$ et $1$.

Pour un problème à $n$ classes, on va vouloir une vraisemblance par classe, on va donc procéder de la façon suivante :

On considère des poids $(w_1, b_1), …, (w_n, b_n)$. Ils définissent un classifieur linéaire.

En effet, si on considère les $z_i$ définis pour tout exemple $x$ par

$$ \begin{cases} z_1 = w_1⋅x + b_1\\ \vdots\\ z_n = w_n⋅x + b_1 \end{cases} $$

On peut choisir la classe $y$ à affecter à $x$ en prenant $y=\operatorname{argmax}\limits_i z_i$

Il reste à normaliser pour avoir des vraisemblances. Pour ça on utilise une fonction très importante : la fonction $\operatorname{softmax}$, définie ainsi :

$$\operatorname{softmax}(z_1, …, z_n) = \left(\frac{e^{z_1}}{\sum_i e^{z_i}}, …, \frac{e^{z_n}}{\sum_i e^{z_i}}\right)$$

Contrairement à la fonction logistique qui prenait un nombre en entrée et renvoyait un nombre, $\operatorname{softmax}$ prend en entrée un vecteur non-normalisé et renvoie un vecteur normalisé.

On définit enfin le classifieur logistique multinomial $f$ de la façon suivante : pour tout exemple $x$, on a

$$f(x) = \operatorname{softmax}(w_1⋅x+b_1, …, w_n⋅x+b_n) = \left(\frac{e^{w_1⋅x+b_1}}{\sum_i e^{w_i⋅x+b_i}}, …, \frac{e^{w_n⋅x+b_n}}{\sum_i e^{w_i⋅x+b_i}}\right)$$

et on choisit pour $x$ la classe

$$y = \operatorname{argmax}\limits_i f_i(x) = \operatorname{argmax}\limits_i \frac{e^{w_i⋅x+b_i}}{\sum_j e^{w_j⋅x+b_j}}$$

Comme la fonction exponentielle est croissante, ce sera la même classe que le classifieur linéaire précédent. Comme pour le cas à deux classe, la différence se fera lors de l'apprentissage. Je vous laisse aller en lire les détails dans Speech and Language Processing, mais l'idée est la même : on utilise la log-vraisemblance négative de la classe correcte comme fonction de coût, et on optimise les paramètres avec l'algo de descente de gradient stochastique.

Un dernier détail ?

Qu'est-ce qui se passe si on prend ce qu'on vient de voir pour $n=2$ ? Est-ce qu'on retombe sur le cas à deux classe vu précédemment ?

Oui, regarde : dans ce cas

$$ \begin{align} f_1(x) &= \frac{e^{w_1⋅x+b_1}}{e^{w_0⋅x+b_0}+e^{w_1⋅x+b_1}}\\ &= \frac{1}{ \frac{e^{w_0⋅x+b_0}}{e^{w_1⋅x+b_1}} + 1 }\\ &= \frac{1}{e^{(w_0⋅x+b_0)-(w_1⋅x+b_1)} + 1}\\ &= \frac{1}{1 + e^{(w_0-w_1)⋅x+(b_0-b_1)}}\\ &= σ((w_0-w_1)⋅x+(b_0-b_1)) \end{align} $$

Autrement dit, appliquer ce qu'on vient de voir pour le cas multinomial, si $n=2$, c'est comme appliquer ce qu'on a vu pour deux classes, avec $w=w_0-w_1$ et $b=b_0-b_1$.

La suite

Vous êtes arrivé⋅e⋅s au bout de ce cours et vous devriez avoir quelques idées de plusieurs concepts importants :

On reparlera de tout ça en temps utile. Pour la suite de vos aventures au pays des classifieurs logistiques, je vous recommande plutôt d'utiliser leur implémentation dans scikit-learn. Maintenant que vous savez comment ça marche, vous pouvez le faire la tête haute. Bravo !

Vous avez aussi découvert les premiers réseaux de neurones de ce cours et ce n'est pas rien !